﻿#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

template<class k, class Compare = less<k>>
void print_set(const set<k, Compare>& s)
{
	/*for (auto& e : s)
		cout << e << ' ';*/
	typename set<k, Compare>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << ' ';
		it++;
	}
	cout << endl;
}

template<class Container>
void print_multiset(const Container& s)
{
	for (auto& e : s)
		cout << e << ' ';
	cout << endl;
}


template<class Container>
void print_map(const Container& m)
{
	//auto it = m.begin();
	typename Container::const_iterator it = m.begin();
	while (it != m.end())
	{
		cout << it->first << ':' << it->second << "   ";
		it++;
	}
	cout << endl;
}

namespace test_set
{
	void test1()
	{
		//去重 + 升序排序
		set<int, less<int>> s1;
		set<int> s2;
		//print_set(s1);

		//去重 + 降序排序
		set<int, greater<int>> s3;

		//调用无参默认构造
		set<int> s4;

		//迭代器区间构造
		vector<int> v = { 1, 5, 5, 10, 7, 3 };
		set<int> s5(v.begin(), v.end());

		//拷贝构造
		set<int> s6 = s5;

		//initializer列表构造
		set<int, greater<int>> s7({ 1, 5, 5, 10, 7, 3 });
		//调用initializer列表构造set<int>临时对象+拷贝构造 ——》优化为直接调用initializer列表构造
		set<int> s8 = { 1, 5, 5, 10, 7, 3 };
		print_set(s7);
	}
	void test2()
	{
		set<char> s;
		//单个数据插入，如果已存在则插入失败
		s.insert('a');
		print_set(s);
		//initializer列表插入
		s.insert({ 'a', 'b', 'b', 'c' });
		print_set(s);
		//迭代器区间插入
		char a[] = { 'z', 'b', 'e' };
		s.insert(a, a + 3);
		print_set(s);
	}
	void test3()
	{
		set<char> s({ 'a' });
		set<char>::iterator it = s.begin();
		//*it = 'b';//不能修改
		it = s.find('b');
		if (it == s.end())
			cout << "找不到" << endl;
		else
			cout << *it << endl;
		auto n = s.count('a');
		if (n == 0)
			cout << "找不到" << endl;
		else
			cout << "找到了，个数为: " << n << endl;
	}
	void test4()
	{
		set<int> s1({ 1, 5, 8, 4 });
		set<int, greater<int>> s2({ 1, 5, 8, 4 });
		//删除一个迭代器位置的值，分别删除s1最小数据、s2最大数据
		s1.erase(s1.begin());
		s2.erase(s2.begin());
		print_set(s1);
		print_set(s2);

		//删除val,val不存在(也就是删除失败)返回0，反之，返回1
		int n = s1.erase(5);
		cout << n << endl;
		print_set(s1);
		n = s1.erase(100);
		cout << n << endl;
		print_set(s1);

		//删除一段迭代器区间的值
		s2.erase(s2.begin(), --s2.end());
		print_set(s2);
	}
	void test5()
	{
		set<int> s;
		for (int i = 1; i <= 9; ++i)
			s.insert(i * 10);
		print_set(s);
		//删除25-60的值
		auto b = s.lower_bound(25);//返回大于等于val的第一个数据的迭代器
		auto e = s.upper_bound(60);//返回大于val的第一个数据的迭代器
		s.erase(b, e);
		print_set(s);
	}
	void test6()
	{
		set<int> s({ 1,1,5, 6, 8,2 });
		//算法库的查找O(N)
		find(s.begin(), s.end(), 5);
		//set自身实现的查找O(log N)
		s.find(5);
	}
}
namespace test_multiset
{
	void test1()
	{
		// 相⽐set不同的是，multiset是排序，但是不去重 
		multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };
		print_multiset(s);

		// 相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个 
		int x;
		cin >> x;
		auto pos = s.find(x);
		while (pos != s.end() && *pos == x)
		{
			cout << *pos << " ";
			++pos;
		}
		cout << endl;
		// 相⽐set不同的是，count会返回x的实际个数 
		cout << s.count(x) << endl;
		// 相⽐set不同的是，erase给值时会删除所有的x 
		s.erase(x);
		print_multiset(s);
	}
}

namespace test_map
{
	void test1()
	{
		//无参构造
		map<string, string> m1;

		//迭代器区间构造
		pair<string, string> arr[] = { {"haha", "哈哈"}, {"totoro", "龙猫"}, {"dudu", "嘟嘟"}, {"dudu","胖熊"} };
		map<string, string> m2(arr, arr + 4);
		print_map(m2);

		//拷贝构造
		auto m3 = m2;
		print_map(m3);

		//initializer列表构造
		map<string, int> m4({ {"西瓜",1},{"冬瓜",2},{"南瓜",3},{"北瓜",4} });
		print_map(m4);
		map<string, int, greater<string>> m5 = { {"西瓜",1},{"冬瓜",2},{"南瓜",3},{"北瓜",4} };
		print_map(m5);
	}
	void test2()
	{
		map<string, int> m;
		m.insert({ "西瓜",1 });
		pair<string, int> p("冬瓜", 2);
		m.insert(p);
		m.insert(pair<string, int>("南瓜", 3));
		m.insert(make_pair("北瓜", 4));
		print_map(m);
		m.insert({ {"黑猫",1},{"白猫",2},{"黄猫",3} });
		print_map(m);
		pair<string, int> arr[] = { {"lcd", 1}, {"totoro", 1}, {"dudu", 2}, {"dudu",5} };
		m.insert(arr, arr + 4);
		print_map(m);
	}
	void test3()
	{
		map<string, int> m;
		vector<string> words = { "hello", "world", "totoro", "world" };
		for (auto& e : words)
		{
			m[e]++;
		}
		for (auto& e : m)
		{
			cout << e.first << ':' << e.second << endl;
		}
	}
}

namespace test_multimap
{
	void test1()
	{
		multimap<string, string> mp;
		mp.insert(make_pair("sort", "排序1"));
		mp.insert({ "sort", "排序2" });
		mp.insert(pair<string, string>("world", "世界"));
		multimap<string, string>::iterator it = mp.begin();
		while (it != mp.end())
		{
			cout << it->first << ':' << it->second << endl;
			it++;
		}
		cout << endl;
		auto ret = mp.equal_range("sort");
		for (auto iit = ret.first; iit != ret.second; ++iit)
		{
			cout << iit->first << ":" << iit->second << endl;
		}
	}
}

int main()
{
	//test_set::test6();
	//test_multiset::test1();
	//test_map::test3();
	test_multimap::test1();
	return 0;
}